package Q3;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int k = sc.nextInt();
        int t = sc.nextInt();

        int n = (int)(1e6 + 1);

        int[] arr = new int[n];

        int count = 1; //下标的数属于第几个区间
        for (int i = 1; i < n; i++) {
            int index = i;
            while (index < n && index < i + k) {
                arr[index] = count;
                index++;
            }
            while (index < n && method(i, index) != 1) {
                //找到了该区间的最右端
                arr[index++] = count;
            }
            if (index < n) {
                arr[index] = count;
                count++;
            } else {
                break;
            }
            i = index;
        }

        while (t > 0) {
            t--;
            int num = sc.nextInt();
            System.out.println(arr[num]);
        }

        sc.close();
    }

    /**
     * 求最小公约数
     * @return
     */
    public static int method(int a, int b) {
        int c = b % a;
        while (c != 0) {
            b = a;
            a = c;
            c = b % a;
        }

        return a;
    }

}
